import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-11-23
 * Time: 13:45
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Main {
    //汉诺塔
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if (n == 1) {
            // 把A中的一个元素删除,转移到C
            C.add(A.remove(A.size() - 1));
            return;
        }
        // 1.把A上的n-1个盘子,借助C转移到B
        dfs(A, C, B, n - 1);
        // 2.A上的最后一个盘子移动到C
        C.add(A.remove(A.size() - 1));
        // 3.把B上的n-1个盘子借助A移动到C
        dfs(B, A, C, n - 1);
    }

    //
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 1.
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
        }
        if (list1.val < list2.val) {
            return list1;
        }
        return list2;
    }

    public ListNode reverseList(ListNode head) {
        // 边界情况
        if (head == null || head.next == null) {
            return head;
        }

        // 1.先反转后面的结点
        ListNode newHead = reverseList(head.next);
        // 2.调整结构
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode ret = swapPairs(head.next.next);
        ListNode nextNode = head.next;
        head.next = ret;
        nextNode.next = head;
        head = nextNode;
        return head;
    }

    public double myPow(double x, int n) {
        if (n < 0) {
            return 1.0 / pow(x, -(long) n);
        }
        return pow(x, (long) n);
    }

    public double pow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double ret = pow(x, n / 2);
        if (n % 2 == 1) {
            return ret * ret * x;
        }
        return ret * ret;
    }
}
